#include "custom_sp.h"

#include <algorithm>
#include <limits>
#include <cassert>

#include <iostream>

using std::string;
using std::vector;
using std::map;

void Dictionary::loadDictionary(std::istream& stream)
{
    while (!stream.eof())
    {
        string str;
        std::getline(stream, str);
        _dictionary[str.length()].push_back(str);
    }

    for (Dict::iterator it = _dictionary.begin();
         it != _dictionary.end(); ++it)
    {
        std::sort(it->second.begin(), it->second.end());
    }
}

void linearSearch(Dictionary::RawDictionary::const_iterator begin,
                  Dictionary::RawDictionary::const_iterator end,
                  int* bestDistance,
                  Dictionary::RawDictionary::const_iterator* bestWord,
                  string word)
{
    for (Dictionary::RawDictionary::const_iterator x = begin;
         x != end; ++x)
    {
        int distance = levenshtein_distance((*x), word);
        if (distance < (*bestDistance))
        {
            *bestDistance = distance;
            *bestWord = x;
        }
    }
}

string Dictionary::nearestNeighbor(const string& word) const
{
    const int wordLength = word.length();

    {
        Dict::const_iterator it = _dictionary.find(wordLength);
        if (it != _dictionary.end())
        {
            if (std::binary_search(it->second.begin(), it->second.end(), word))
                return word;
        }
    }

    int maxLength = 0;
    for (Dict::const_iterator it = _dictionary.begin();
         it != _dictionary.end(); ++it)
    {
        if (maxLength < it->first)
            maxLength = it->first;
    }

    int bestDistance = std::numeric_limits<int>::max();
    RawDictionary::const_iterator bestWord;

    for (int delta = 0; 
         (wordLength + delta <= maxLength) || (wordLength - delta > 0); 
         ++delta)
    {
        if (bestDistance > delta)
        {
            Dict::const_iterator it = _dictionary.find(wordLength + delta);
            if (it != _dictionary.end())
                linearSearch(it->second.begin(), it->second.end(), 
                             &bestDistance, &bestWord, word);

            if ((delta > 0) && (wordLength > delta))
            {
                Dict::const_iterator it = _dictionary.find(wordLength - delta);
                if (it != _dictionary.end())
                    linearSearch(it->second.begin(), it->second.end(), 
                                 &bestDistance, &bestWord, word);
            }
        }
    }

    return (*bestWord);
}
